package com.barry.algorithm.sort;

/**
 * 类功能描述：插入排序算法
 *
 * @author WangXueXing create at 19-9-4 下午4:29
 * @version 1.0.0
 */
public class InsertionSort {
    /**
     * 插入排序算法
     * 介绍：
     * 插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
     *
     * 步骤：
     * 从第一个元素开始，该元素可以认为已经被排序
     * 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
     * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 将新元素插入到该位置后
     * 重复步骤2~5
     * @param a 被排序的数组
     * 最坏情况：输入数组已反向排序  O（n2）； 最好情况：输入数组已排序  O（n）；平均情况：O（n2）
     * 由于插入排序其内层循环非常紧凑，对于小规模输入，插入排序是一种非常快的排序算法
     */
    public static void insertSort(int[] a){
        int j;
        for(int i=1;i<a.length;i++){
            int temp = a[i];
            for(j=i;j>0;j--){
                if(temp < a[j-1]){
                    a[j] = a[j-1]; //将所有在nums[i]之前的大于nums[i]的值都往后移一位
                }
                else break;
            }
            //移完所有大于nums[i]的值后，j刚好指向最靠前一个大于nums[i]的位置
            a[j] = temp;
        }
        System.out.println("插入排序：");
        for (int i : a) {
            System.out.print(i+" ");
        }
    }

    /**
     * 希尔排序算法
     * 介绍：
     * 希尔排序，也称递减增量排序算法，实质是分组插入排序。由 Donald Shell 于1959年提出。希尔排序是非稳定排序算法。
     * 希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
     * @param a 被排序的数组
     * 最坏情况：O（n2） 使用Hibbard增量的最坏情况：O（n^3/2）
     */
    public static void shellSort(int[] a){
        int len = a.length;
        int increment;
        int temp,i,j;
        for(increment = len/2;increment > 0;increment /= 2){ //增量为len/2 len/4 len/8.....1
            for(i=increment;i<len;i++){ //对每个子序列进行插入排序
                temp = a[i];
                for(j=i;j>=increment;j -= increment){
                    if(temp < a[j-increment]){
                        a[j] = a[j-increment];
                    }
                    else
                        break;
                }
                a[j] = temp;
            }
        }
        System.out.println("希尔排序：");
        for (int k : a) {
            System.out.print(k+" ");
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{2,3,6,4,7,5,1};
        insertSort(a);
        shellSort(a);
    }
}
